const { ListNode, LinkedList } = require('../2. 链表/1. 链表基础/1. 建立线性链表.js')
//  给定一个链表数组，每个链表都已经按照升序排列,要求，将所有链表合并到一个升序链表中，返回合并后的链表

// 思路，归并排序的思路，不断将链表数组一分为二，在归并的过程中合并两个有序链表

function mergeKLists(lists) {
    if (!lists || lists.length === 0) {
        return null
    }
    return mergeSort(lists, 0, lists.length - 1)
}

function mergeSort(lists, left, right) {
    if (left === right) {
        return lists[left]
    }
    let mid = left + Math.floor((right - left) / 2)
    let leftNode = mergeSort(lists, left, mid)
    let rightNode = mergeSort(lists, mid + 1, right)
    return merge(leftNode, rightNode)
}

function merge(node1, node2) {
    let dummyHead = new ListNode(0)
    let cur = dummyHead
    while (node1 && node2) {
        if (node1.val < node2.val) {
            cur.next = node1
            // 要及时更新node1，为了下一次链表更新
            node1 = node1.next
        } else {
            cur.next = node2
            node2 = node2.next
        }
        cur = cur.next
    }
    if (node1) {
        cur.next = node1
    }
    if (node2) {
        cur.next = node2
    }
    return dummyHead.next
}

let lists = [new LinkedList([1,4,5]).head, new LinkedList([1,3,4]).head, new LinkedList([2, 6]).head]
let result = mergeKLists(lists)
// let result = mergeKLists([])
console.log(result)